This invention relates to computer operation, and more particularly to a method of reducing the cache miss rate in a computer system using virtual memory management.
The performance of CPUs has far outstripped memory system performance in the development of computer hardware technology. Caches, which are small, fast memories a fraction of the size of main memory, are used to decrease the effective memory access times. A cache stores a copy of recently-used data for rapid access should the data be needed again, and, for many programs, a cache greatly improves the processing speed of the computer system. However, some programs exhibit poorer than expected performance, or run-to-run performance variations due to a phenomena termed "cache thrashing."
The simplest and fastest (and hence most popular) caches severely limit the number of cache locations where a particular data item can reside. For example, a direct-mapped cache has only one location where a data item may be stored. Cache thrashing occurs when two or more heavily used data items map to the same cache location, and these data items are used by a program in a cyclic manner, as in a loop. As each data is used, it displaces its predecessor, causing a relatively slow main memory access. Cache thrashing can severely degrade program run times by forcing many main memory accesses, and thrashing also increases the system interconnect bandwidth required by a system to obtain reasonable performance.
Cache thrashing occurs on a chance basis when the operating system randomly assigns data items to physical memory pages. The data items in this context may be operating system code or data structures, or the code or data of any of the programs the operating system is managing.
In the past, general-purpose operating systems such as UNIX or VMS have made no effort to assign physical memory pages in other than "random" order. This pseudo-random order of physical memory assignments is obtained incidentally via the complex process of virtual memory management and its re-ordering of physical memory pages on a free page list.
The process of assigning virtual memory pages to physical memory pages also defines the subset of CPU cache locations where this data can reside, as cache locations are selected as a function of physical page address, using a cache tag which is part of the physical address. Current operating systems have no mechanism for favoring the selection of one physical page over another to reduce the likelihood of cache thrashing, and no mechanism to detect if a group of physical pages are cache thrashing and remap one or more of the thrashing pages to new physical pages to alleviate the problem.
The random assignment of virtual to physical memory pages is very likely to produce a mapping with several cache locations that have one or more physical pages mapped to them. This problem becomes particularly acute in direct-mapped caches, in which each page can only reside in a single cache location. This physical page selection process can be closely modeled as a "random selection with replacement" probability problem. For example, a 256-entry cache 25% filled has on the average six cache locations with two or more physical pages mapped to them. In this scenario, a very few physical memory pages can be expected to result in an inequitably large percentage of the cache misses. In other words, the cache is being utilized in very inefficient manner.